#include<time.h>
#include<math.h>
#include<malloc.h>
#include<stdio.h>
#include<cstdlib>
#include<fstream>
#include<iostream>
#include<sstream>
#include<vector>
#include<set>

using namespace std;

int input_dimension;
int number_of_items;
int num_of_cluster;

ifstream inputFile;

int getInput(double* one_input)
{
	string line;
	if (getline(inputFile,line))
	{
		istringstream iss(line);
		int i=0;
		do
		{
			if (i>input_dimension-1) break;
			string sub;
			iss >>sub;
			one_input[i++]=atof(sub.c_str());
		} while (iss);
		return 1;
	}
	else return 0;
}

double getDistance(double * weight,double * input_vector)
{
	double sum=0;
	for (int i=0;i<input_dimension;i++)
	{
		sum+=(weight[i]-input_vector[i])*(weight[i]-input_vector[i]);
	}
	return sum;
}

double theta(double distance)
{
	if (distance<0.0000001) return 2;
	else return 1/distance;
}

int main(int argc, char * argv[])
{
	if (argc<4) 
	{
		printf("usage: ./k-means input_dimension num_of_cluster input_file_name\n\n");
		return 1;
	}
	
	inputFile.open("input");
	string line;
	srand( (unsigned)time( NULL ));

	printf("k-means cluster\n----------------------\nitems:\n");

	input_dimension=atoi(argv[1]);
	num_of_cluster=atoi(argv[2]);

	vector<double*> centers;
	vector<double*> old_centers;

	vector<double*> items;

	double *one_input;
	one_input=(double*)malloc(sizeof(double)*input_dimension);
	while (getInput(one_input))
	{
		for (int j=0;j<input_dimension;j++)
		{
			printf("%f\t",one_input[j]);
		}
		printf("\n");

		items.push_back(one_input);
		
		one_input=(double*)malloc(sizeof(double)*input_dimension);
	}
	free(one_input);

	printf("init centers:\n");
	set<int> init_centers;

	for (int i=0;i<num_of_cluster;i++)
	{
		int init_center=rand()%(num_of_cluster);
		while (init_centers.find(init_center)!=init_centers.end())
		{
			init_center=rand()%(items.size());
		}
		init_centers.insert(init_center);
		cout<<init_center<<":";
		one_input=(double*)malloc(sizeof(double)*input_dimension);
		for (int j=0;j<input_dimension;j++)
		{
			one_input[j]=items[init_center][j];
			printf("%f\t",one_input[j]);
		}
		printf("\n");
		centers.push_back(one_input);
	}

	vector<int>  clusters[num_of_cluster];
	
	double diffence=1000;

	int turns=0;
	while (diffence>0.1)	
	{
		diffence=0;
		printf("turn %d:\n",++turns);
		for (int i=0;i<num_of_cluster;i++)
		{
			clusters[i].clear();
		}

		for (int i=0;i<items.size();i++)	
		{
			int best_center;
			double min_distance=1000;
			for (int j=0;j<centers.size();j++)
			{
				double distance=getDistance(items[i],centers[j]);
				if (distance<min_distance) 
				{
					best_center=j;
					min_distance=distance;
				}
			}
			clusters[best_center].push_back(i);
		}

		for (int i=0;i<num_of_cluster;i++)
		{
			double * new_center=(double*)malloc(sizeof(double)*input_dimension);
			for (int j=0;j<input_dimension;j++)
			{
				new_center[j]=0;
			}
			printf("\tcluster %d:\n",i);
			for (int j=0;j<clusters[i].size();j++)
			{
				printf("\t\titem %d:",j);
				for (int p=0;p<input_dimension;p++)
				{
					printf("%f\t",items[clusters[i][j]][p]);
					new_center[p]+=items[clusters[i][j]][p]/clusters[i].size();
				}
				printf("\n");
			}

			for (int j=0;j<input_dimension;j++)
			{
				diffence+=fabs(new_center[j]-centers[i][j]);
				centers[i][j]=new_center[j];
			}
		}	
	}

	inputFile.close();
	return 0;
}


